package com.dys.datastructuresandalgorithm.bubblesort;

/**
 * @className: com.dys.datastructuresandalgorithm.bubblesort.BubbleSort
 * @description: 冒泡排序:每次交换都是相邻的
 * @author: pine cone
 * @version: v1.0.0
 * @createTime: 2024/05/28 下午11:07
 */
public class BubbleSort {

    /**
     * 交换方法：交换一个整型数组中指定下标的两个元素。
     *
     * @param array  需要进行元素交换的整形数组
     * @param first  需要交换的第一个元素的下标。
     * @param second 需要交换的第二个元素的下标。
     */
    public static void swap(int[] array, int first, int second) {
        // 用临时变量存储array数组中第second个元素的值
        int temp = array[second];

        // 将array数组中第second个元素的值更新为第first个元素的值
        array[second] = array[first];

        // 将array数组中第first个元素的值更新为temp变量的值。
        array[first] = temp;
    }

    /**
     * 冒泡排序：对输入的整型数组进行排序-->从小到大
     *
     * @param array 等待输入的整型数组
     */
    public static void bubbleSort1(int[] array) {
        // 边界处理: 若只有一个元素or没有元素,则不进行排序
        if (array == null || array.length < 2) {
            return;
        }

        // 获取数组的长度
        int n = array.length;
        // 从数组的最后一个元素开始向前遍历，直到第一个元素。其中for循环做的事情: 0 ~ n-1 | 0 ~ n-2 | 0 ~ n-3 ...| 0 ~ end
        for (int end = n - 1; end >= 0; end--) {
            // 内层循环使用变量second从第二个元素开始，遍历到当前外层循环的位置end。
            // 内层for循环做一件事儿(比较两个数的大小)：0 1 | 1 2 | 2 3 | 3 4 | end-1 end
            for (int second = 1; second <= end; second++) {
                // 比较相邻的两个元素，如果前一个元素比后一个元素大，就交换它们的位置。-->从小到大排列
                if (array[second - 1] > array[second]) {
                    swap(array, second - 1, second);
                }
            }
        }
    }

    /**
     * 冒泡排序：对输入的整型数组进行排序-->从大到小
     *
     * @param array 等待输入的整型数组
     */
    public static void bubbleSort2(int[] array) {
        // 边界处理: 若只有一个元素or没有元素,则不进行排序
        if (array == null || array.length < 2) {
            return;
        }

        // 获取数组的长度
        int n = array.length;
        // 从数组的最后一个元素开始向前遍历，直到第一个元素。其中for循环做的事情: 0 ~ n-1 | 0 ~ n-2 | 0 ~ n-3 ...| 0 ~ end
        for (int end = n - 1; end >= 0; end--) {
            // 内层循环使用变量second从第二个元素开始，遍历到当前外层循环的位置end。
            // 内层for循环做一件事儿(比较两个数的大小)：0 1 | 1 2 | 2 3 | 3 4 | end-1 end
            for (int second = 1; second <= end; second++) {
                // 比较相邻的两个元素，如果前一个元素比后一个元素大，就交换它们的位置。-->从大到小排列
                // 判断两个位置之间的数字要不要交换，第一次是：0和1比较
                if (array[second - 1] < array[second]) {
                    swap(array, second - 1, second);
                }
            }
        }
    }

    /**
     * 打印方法：打印整型数组元素
     *
     * @param array 等待打印的整型数组
     */
    public static void printArray(int[] array) {
        for (int i = 0; i < array.length; i++) {
            System.out.print(array[i] + " ");
        }
        System.out.println();
    }


    /**
     * 冒泡排序：每次交换都是相邻(从小到大)
     *
     * @param arr 等待排序的数组
     */
    public static void bubbleSort(int[] arr) {
        int n = arr.length;
        // 用于优化，检查本轮是否进行了交换
        boolean swapped;

        for (int i = 0; i < n - 1; i++) {
            swapped = false;
            for (int j = 0; j < n - i - 1; j++) {
                if (arr[j] > arr[j + 1]) {
                    // 交换 arr[j+1] 和 arr[j]
                    int temp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = temp;
                    swapped = true;
                }
            }
            // 如果在某轮遍历中没有发生交换，说明数组已经是有序的了，可以提前结束排序
            if (!swapped) {
                break;
            }
        }
    }

    public static void main(String[] args) {
        int[] arr = {66, 33, 22, 11, 22, 44, 99};
        System.out.println("====排序之前的数组元素===========");
        printArray(arr);
        bubbleSort1(arr);
        System.out.println("====排序之后的数组元素===========");
        printArray(arr);
    }
}
